// https://leetcode.cn/problems/dungeon-game/description/

// 算法思路总结：
// 1. 使用一维DP反向计算最小初始血量
// 2. 从终点开始倒推，确保任何位置血量≥1
// 3. 状态转移：min(右方,下方)需求 - 当前值，并取max(1,...)
// 4. 时间复杂度：O(mn)，空间复杂度：O(n)

#include <iostream>
using namespace std;

#include <vector>
#include <algorithm>

class Solution 
{
public:
    const int INF = 0x3f3f3f3f;
    int calculateMinimumHP(vector<vector<int>>& dungeon) 
    {
        int m = dungeon.size(), n = dungeon[0].size();
        vector<int> dp(n + 1, INF);
        
        dp[n - 1] = max(1, 1 - dungeon[m - 1][n - 1]);
        for (int i = n - 2 ; i >= 0 ; i--)
            dp[i] = max(1, dp[i + 1] - dungeon[m - 1][i]);

        for (int i = m - 2; i >= 0 ; i--)
        {
            for (int j = n - 1 ; j >= 0 ; j--)
            {
                dp[j] = min(dp[j], dp[j + 1]) - dungeon[i][j];
                dp[j] = max(1, dp[j]);
            }
        }
        return dp[0];
    }
};

int main()
{
    vector<vector<int>> vv1 = {{-2,-3,3}, {-5,-10,1}, {10,30,-5}};
    vector<vector<int>> vv2 = {{0}};

    Solution sol;

    cout << sol.calculateMinimumHP(vv1) << endl;
    cout << sol.calculateMinimumHP(vv2) << endl;

    return 0;
}